package sort;
//三元取中优化
public class quick_plus {
    public static void a(int [] arr,int left,int right){
        if (left>=right){
            return;
        }
        int div=b(arr,left,right);
//        左边递归
        a(arr,left,div);
//        右边递归
        a(arr,div+2,right);
    }
    public static int b(int[]arr,int left,int right){

        int i=left,j=right,k=(left+right)/2;
        if (arr[i]>arr[j]){
            if (arr[k]>=arr[i]){
                ;
            } else if (arr[k]<arr[i]) {
                swap(arr,i,(arr[k]>=arr[j]?k:j));
            }
        }else if (arr[i]<arr[j]){
            if (arr[k]>=arr[j]){
                swap(arr,i,j);
            } else if (arr[j]>arr[k]) {
                swap(arr,i,(arr[k]>=arr[i]?k:i));
            }
        }
        left=i;
        right=j;
        while(i<j){
            while (i<j&&arr[j]>=arr[left]){
                j--;
            }
            while (i<j&&arr[i]<=arr[left]){
                i++;
            }
            swap(arr,i,j);
        }
        swap(arr,left,i);
        return i-1;
    }
    public static void swap(int[]arr,int a,int b){
        int temp=arr[a];
        arr[a]=arr[b];
        arr[b]=temp;
    }
}
